Shapley Interaction Index 논문 리뷰(작성중)
| Venue | Link |
|---|---|
| International Journal of Game Theory, 1999 | Springer |
1 Introduction
Grabisch and Roubens [2]의 논문은 cooperative game에서 player들 사이의 interaction을 어떻게 정의할 것인가를 다룬다. 여기서 cooperative game은 player들의 집합 N이 있고, 각 coalition S \subseteq N에 대해 worth v(S)가 주어지는 setting이다.
v: 2^N \to \mathbb{R}, \qquad v(\emptyset)=0
Shapley value는 각 player가 game에서 평균적으로 얼마나 기여하는지를 말해준다 [5]. 하지만 논문은 Shapley value만으로는 설명하지 못하는 것이 있다고 본다. 예를 들어 두 player i,j가 있다고 하자. 각각 혼자 있을 때는 worth가 작지만, 둘이 함께 있을 때 worth가 크다면 두 player 사이에는 positive interaction이 있다. 반대로 둘이 함께 있을 때 worth가 각각의 합보다 작다면 negative interaction이 있다.
단순히 보면 다음 값을 비교하면 될 것처럼 보인다.
v(\{i,j\}) - v(\{i\}) - v(\{j\})
하지만 논문은 이것만으로는 부족하다고 본다. 왜냐하면 i와 j의 interaction은 빈 coalition에서만 생기는 것이 아니라, 다른 coalition S에 i,j가 들어갈 때도 나타날 수 있기 때문이다. 그래서 pairwise interaction의 핵심 quantity는 다음과 같은 second-order difference가 된다.
v(S \cup \{i,j\}) - v(S \cup \{i\}) - v(S \cup \{j\}) + v(S)
논문은 이 직관을 임의의 coalition S로 확장하고, 이를 Shapley value나 Banzhaf value처럼 axiom으로 정당화하려고 한다. 즉 논문의 목표는 다음이다.
Value가 single player의 평균 기여도를 정의한다면, interaction index는 coalition 전체의 상호작용 정도를 정의해야 한다.
2 The Shapley and Banzhaf values
2.1 Notations and definitions
논문은 바로 interaction index를 정의하지 않고, 먼저 Shapley value와 Banzhaf value의 axiomatization을 복습한다. 이 복습은 단순한 배경 설명이 아니라, 뒤에서 interaction index의 axiom을 만들기 위한 template 역할을 한다.
Game v에서 player i의 value는 대략 다음 형태를 가진다.
\phi_v(i) = \sum_{T \subseteq N \setminus \{i\}} p_t(n) \left[ v(T \cup \{i\}) - v(T) \right]
여기서 t=|T|이다. 즉 value는 player i가 여러 coalition T에 들어갈 때의 added worth를 weighted average한 것이다.
2.2 Axioms
논문이 사용하는 주요 axiom은 다음과 같다.
Linearity. Game을 더하면 value도 더해져야 한다.
\phi_{v+w} = \phi_v + \phi_w
Dummy. Player i가 항상 독립적으로만 기여한다면, 즉 모든 S \subseteq N\setminus\{i\}에 대해
v(S \cup \{i\}) = v(S) + v(\{i\})
이면 i의 value는 v(\{i\})여야 한다.
Symmetry. Player 이름을 바꾸어도 구조가 같으면 value도 이름만 바뀌어야 한다.
Efficiency. 전체 worth가 player들에게 모두 분배되어야 한다.
\sum_{i \in N} \phi_v(i) = v(N)
2.3 The Shapley and Banzhaf values
이 axiom들을 만족하는 유일한 value가 Shapley value이다. 논문은 Shapley value를 다음과 같이 쓴다.
\phi^S_v(i) = \sum_{T \subseteq N \setminus \{i\}} \frac{(n-t-1)!t!}{n!} \left[ v(T \cup \{i\}) - v(T) \right]
Banzhaf value도 비슷하지만 weight가 다르다.
\phi^B_v(i) = \frac{1}{2^{n-1}} \sum_{T \subseteq N \setminus \{i\}} \left[ v(T \cup \{i\}) - v(T) \right]
즉 Shapley value는 coalition size에 따라 weight가 달라지고, Banzhaf value는 모든 T를 같은 weight로 평균낸다. 논문은 이 두 value가 뒤에서 각각 Shapley interaction index와 Banzhaf interaction index로 확장된다고 본다.
3 Axiomatization of the interaction index
3.1 Interaction index as a set function
논문 3절에서 본격적으로 interaction index를 axiomatize한다. Notation은 다음과 같다.
I_v(S)
이는 game v에서 coalition S \subseteq N 안의 player들이 얼마나 interaction하는지를 나타내는 값이다. 여기서 중요한 점은 I_v가 player 하나에 대한 함수가 아니라, subset 전체에 대한 set function이라는 점이다.
논문은 처음에 흥미로운 문제를 짚는다. 직관적으로 interaction은 적어도 두 player 사이에서 의미가 있다. 그러면 I_v(\{i\})나 I_v(\emptyset)는 어떻게 해석해야 할까?
논문은 interaction index를 모든 subset에 대해 정의되는 set function으로 만들기 위해 singletons도 포함한다. 그리고 나중에 I_v(\{i\})가 기존 value와 연결되도록 만든다. 즉, single player의 interaction은 그 player의 value로 해석된다. 이렇게 해야 interaction index가 value의 extension이 된다.
3.2 Linearity axiom
첫 번째 axiom은 interaction version의 linearity이다.
LI. 각 subset S에 대해 I_v(S)는 game v에 대해 linear해야 한다.
이 axiom만으로도 I_v(S)는 coalition worth들의 linear combination으로 쓸 수 있다.
I_v(S) = \sum_{T \subseteq N} \alpha^S_T v(T)
아직 interaction의 형태가 정해진 것은 아니다. 하지만 모든 interaction index가 game worth들의 선형 결합이어야 한다는 출발점을 만든다.
3.3 Dummy axiom and discrete derivative
다음은 dummy axiom이다. 논문은 interaction version의 dummy axiom을 사용한다. 직관은 간단하다. 만약 player i가 dummy라면, i는 다른 player들과 interaction하지 않아야 한다. 따라서 i를 포함하고 크기가 2 이상인 coalition S에 대해서는 interaction이 0이어야 한다.
이 조건을 linearity와 함께 쓰면 interaction index의 형태가 크게 좁혀진다. 논문은 Proposition 2에서 다음 형태를 얻는다.
I_v(S) = \sum_{T \subseteq N \setminus S} p^S_T \delta_S v(T \cup S)
여기서 \delta_S는 S에 대한 discrete derivative이다.
\delta_S v(T \cup S) = \sum_{L \subseteq S} (-1)^{s-l} v(T \cup L)
여기서 s=|S|, l=|L|이다.
이 식이 논문의 중요한 전환점이다. 처음에는 interaction index를 임의의 linear combination으로 생각했지만, dummy axiom을 넣으면 interaction은 자연스럽게 inclusion-exclusion 형태의 discrete derivative로 표현된다.
Pairwise case에서 이 식은 다음으로 줄어든다.
\delta_{\{i,j\}}v(T \cup \{i,j\}) = v(T \cup \{i,j\}) - v(T \cup \{i\}) - v(T \cup \{j\}) + v(T)
즉 introduction에서 직관적으로 제시한 pairwise interaction이 axiom에서 다시 나온다.
3.4 Symmetry axiom
아직 p^S_T는 subset S와 context T에 따라 다를 수 있다. 논문은 symmetry axiom을 추가한다.
SI. Player 이름을 permutation해도 interaction index는 그 permutation에 맞게 변해야 한다.
이 axiom을 넣으면 coefficient는 특정 player 이름에 의존할 수 없다. 따라서 p^S_T는 S와 T의 실제 원소가 아니라 크기에만 의존한다. 논문은 이를 다음처럼 쓴다.
p^S_T = p^s_t(n)
여기서 s=|S|, t=|T|, n=|N|이다. 따라서 LI, DI, SI를 만족하는 interaction index는 다음 일반형을 갖는다.
I_v(S) = \sum_{T \subseteq N \setminus S} p^s_t(n) \delta_S v(T \cup S)
이 시점까지 논문은 아직 Shapley interaction이나 Banzhaf interaction을 특정하지 않았다. 다만 모든 reasonable interaction index가 weighted discrete derivative 형태를 가져야 함을 보인 것이다.
3.5 Recursive axioms
이제 논문은 interaction index를 기존 value와 연결해야 한다. 그렇지 않으면 p^s_t(n)가 너무 자유롭다.
논문은 먼저 pair \{i,j\}를 하나의 combined player [ij]로 묶은 reduced game을 생각한다. 직관은 다음과 같다.
i와 j가 positive interaction을 가지면, 둘을 하나로 묶은 player [ij]의 value는 단순히 i의 value와 j의 value를 더한 것보다 커야 한다.
반대로 negative interaction이면 더 작아야 한다. 따라서 reduced game에서 [ij]의 value는 두 player의 개별 value와 둘 사이의 interaction을 함께 반영해야 한다.
논문은 이 생각을 recursive axiom으로 일반화한다. 핵심 메시지는 다음이다.
Coalition S의 interaction은 S 안의 player들을 묶거나 풀었을 때의 lower-order interaction과 일관되어야 한다.
논문은 두 가지 recursive axiom R1, R2를 제시하고, LI, DI, SI 아래에서 둘이 equivalent임을 보인다. 이 recursive axiom이 중요한 이유는 interaction index를 value에 묶어주기 때문이다. 즉, Shapley value를 singletons에서 선택하면 Shapley interaction index가 결정되고, Banzhaf value를 선택하면 Banzhaf interaction index가 결정된다.
논문은 recursive axiom으로부터 다음 계수 관계를 얻는다.
p^s_t(n) = p^1_t(n-s+1)
이는 order s interaction의 coefficient가 single-player value 쪽 coefficient로 환원된다는 뜻이다. 이 결과 때문에 interaction index는 value의 extension이 된다.
3.6 Main theorem
논문의 main theorem은 다음 두 index를 characterizes한다.
첫째, Shapley interaction index이다.
I^S_v(S) = \sum_{T \subseteq N \setminus S} \frac{(n-t-s)!t!}{(n-s+1)!} \sum_{L \subseteq S} (-1)^{s-l} v(T \cup L)
이를 \delta_S notation으로 쓰면 더 간단하다.
I^S_v(S) = \sum_{T \subseteq N \setminus S} \frac{(n-t-s)!t!}{(n-s+1)!} \delta_S v(T \cup S)
TreeSHAP-IQ 논문에서 쓰는 SII 식은 이 식을 binomial coefficient 형태로 다시 쓴 것이다 [4].
\frac{(n-t-s)!t!}{(n-s+1)!} = \frac{1}{(n-s+1){n-s \choose t}}
따라서 다음과 같이 쓸 수 있다.
I_{\mathrm{SII}}(f,S) = \sum_{T \subseteq N \setminus S} \frac{1}{(n-|S|+1){n-|S| \choose |T|}} \delta_S(f,T)
둘째, Banzhaf interaction index이다.
I^B_v(S) = \frac{1}{2^{n-s}} \sum_{T \subseteq N \setminus S} \sum_{L \subseteq S} (-1)^{s-l} v(T \cup L)
즉 Shapley interaction과 Banzhaf interaction의 차이는 value case와 비슷하다. Shapley interaction은 context size에 따라 Shapley-style weight를 주고, Banzhaf interaction은 모든 context를 균등하게 평균낸다.
논문의 main theorem은 단순히 formula를 제시하는 것이 아니다. 이 formula들이 LI, DI, SI, 그리고 recursive axiom을 만족하는 유일한 interaction index임을 보인다.
4 Alternative axiomatization of the Banzhaf interaction index
논문 4절은 Banzhaf interaction index에 대한 alternative axiomatization을 제시한다. 여기서는 recursive axiom을 쓰지 않고, generalized 2-efficiency axiom과 limit condition을 사용한다.
Generalized 2-efficiency의 직관은 다음과 같다. 두 player i,j를 combined player [ij]로 묶었을 때, 어떤 coalition과 [ij]의 interaction은 원래 game에서 i를 넣은 interaction과 j를 넣은 interaction의 합과 맞아야 한다.
또 limit condition은 coalition S만 남은 game에서는 interaction이 discrete derivative 자체와 같아야 한다는 조건이다.
I^S_v(S) = \delta_S v(S)
이 두 조건과 LI, DI, SI를 사용하면 Banzhaf interaction의 coefficient가 모든 context에 대해 같아진다.
p^s_t(n) = \frac{1}{2^{n-s}}
따라서 Banzhaf interaction index가 나온다.
이 절은 Shapley interaction보다는 Banzhaf interaction 쪽에 초점이 있다. 하지만 논문의 전체 흐름에서는 중요하다. 왜냐하면 interaction index가 recursive axiom만으로 설명되는 것이 아니라, efficiency류 axiom으로도 characterization될 수 있음을 보여주기 때문이다.
5 Expression of interaction indices in terms of pseudo-Boolean functions
논문 5절은 interaction index를 pseudo-Boolean function, 더 정확히는 game의 multilinear extension으로 표현한다. 이 부분은 앞의 axiom 논의보다 해석적이다.
Game v는 subset S \subseteq N에 값을 주는 set function이다. 이를 Boolean vector의 꼭짓점 위 함수로 볼 수 있다. 예를 들어 S에 대응하는 vector \alpha_S \in \{0,1\}^n를 다음처럼 둔다.
(\alpha_S)_j = \begin{cases} 1, & j \in S \\ 0, & j \notin S \end{cases}
그러면 g(\alpha_S)=v(S)가 되도록 v를 [0,1]^n 위의 multilinear function g로 확장할 수 있다. 논문은 이를 multilinear extension이라고 부른다.
g(x_1,\ldots,x_n) = \sum_{S \subseteq N} a(S) \prod_{i \in S} x_i
여기서 a(S)는 dividend 또는 Mobius transform coefficient이다. 이는 game을 다른 basis로 표현한 것이다.
이 관점에서 interaction index는 game의 또 다른 representation이다. 논문은 interaction index도 dividend처럼 game을 표현하는 invertible transform으로 볼 수 있다고 말한다. 즉 interaction index는 단순한 보조 score가 아니라, game의 구조를 다른 좌표계에서 본 것이다.
이 부분은 TreeSHAP-IQ와도 연결된다. TreeSHAP-IQ는 polynomial arithmetic을 사용해 Shapley interaction을 계산한다. Grabisch and Roubens 논문은 이미 interaction index가 pseudo-Boolean/multilinear representation과 연결된다는 관점을 제시하고 있다. 즉, later XAI 알고리즘에서 polynomial이 등장하는 것은 우연이 아니다.
ML explanation 관점에서 읽기
원 논문은 cooperative game theory 논문이다. 따라서 player, coalition, worth라는 언어로 쓰여 있다. 이를 ML explanation으로 옮기면 다음처럼 대응된다.
| Cooperative game | ML explanation |
|---|---|
| player | feature |
| coalition S | feature subset |
| worth v(S) | subset S만 알려졌을 때의 model output |
| value \phi_v(i) | feature attribution |
| interaction index I_v(S) | feature interaction attribution |
이 대응을 사용하면 SII는 feature subset S의 interaction score가 된다. 다만 ML에서는 v(S), 즉 feature subset만 있을 때의 model output을 어떻게 정의할지가 추가 문제로 생긴다. TreeSHAP은 tree path distribution을 사용하고, interventional SHAP은 background distribution을 사용한다 [1, 3].
따라서 ML에서 SII를 쓸 때는 두 층을 구분해야 한다.
- Grabisch and Roubens 논문이 정의한 game-theoretic interaction index
- ML model에서 subset output f(x,S)를 어떻게 만들 것인가
TreeSHAP-IQ는 두 번째 문제 중 tree ensemble case를 다루면서, 첫 번째 층의 SII와 n-SII를 효율적으로 계산한다 [4].
정리
이 논문의 흐름은 다음과 같다.
- Shapley value는 player 하나의 평균 added worth를 설명하지만, player들 사이의 cooperation/interference는 설명하지 못한다.
- Pairwise interaction은 second-order difference에서 출발하고, higher-order interaction은 discrete derivative \delta_S로 일반화된다.
- LI, DI, SI를 넣으면 interaction index는 weighted discrete derivative 형태가 된다.
- Recursive axiom을 넣으면 interaction index가 기존 value와 연결된다.
- Shapley value를 선택하면 Shapley interaction index가, Banzhaf value를 선택하면 Banzhaf interaction index가 유일하게 결정된다.
- Banzhaf interaction은 recursive axiom 대신 generalized 2-efficiency와 limit condition으로도 characterize할 수 있다.
- 마지막으로 interaction index는 multilinear extension/pseudo-Boolean representation 관점에서 game의 또 다른 표현으로 해석된다.
따라서 SII는 단순히 “SHAP interaction 공식”이 아니다. 원래는 cooperative game에서 coalition interaction을 axiom으로 정당화하려는 시도이고, TreeSHAP-IQ 같은 XAI 논문은 이 game-theoretic index를 model explanation에 가져와 효율적으로 계산하는 것이다.